# -*- encoding: utf-8 -*-
alphabet_size = 256


def hash(pattern):
    p_len = len(pattern)
    p_hash = 0
    for i in range(p_len):
        p_hash = p_hash * alphabet_size + ord(pattern[i])
    return p_hash


def rabin_karp(pattern, text):
    p_len = len(pattern)
    t_len = len(text)
    if p_len > t_len:
        return False

    p_hash = hash(pattern)

    for i in range(t_len - p_len + 1):
        t_hash = hash(text[i: i + p_len])
        if t_hash == p_hash:
            return True

    return False


def test_rabin_karp():
    """
    >>> test_rabin_karp()
    Success.
    """
    # Test 1)
    pattern = "abc1abc12"
    text1 = "alskfjaldsabc1abc1abc12k23adsfabcabc"
    text2 = "alskfjaldsk23adsfabcabc"
    assert rabin_karp(pattern, text1) and not rabin_karp(pattern, text2)

    # Test 2)
    pattern = "ABABX"
    text = "ABABZABABYABABX"
    assert rabin_karp(pattern, text)

    # Test 3)
    pattern = "AAAB"
    text = "ABAAAAAB"
    assert rabin_karp(pattern, text)

    # Test 4)
    pattern = "abcdabcy"
    text = "abcxabcdabxabcdabcdabcy"
    assert rabin_karp(pattern, text)

    # Test 5)
    pattern = "Lü"
    text = "Lüsai"
    assert rabin_karp(pattern, text)
    pattern = "Lue"
    assert not rabin_karp(pattern, text)
    print("Success.")


if __name__ == '__main__':
    print(hash('abc'))
    test_rabin_karp()
